package 二分查找.easy;

import java.util.Random;

/**
 * 1. 问题描述
 *       求出x的平方根
 *       计算并返回 x 的平方根，其中 x 是非负整数。
 *       由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去
 *
 * 2. 算法分析
 *      1. 二分法
 *      2. 牛顿切线法
 *
 * 3. 代码实现
 */
@SuppressWarnings("all")
public class x的平方根 {
    public static void main(String[] args) {
        System.out.println(FloatSqrt(8, 0.00001));
    }

    /**
     * 求出num的平方根  这个平方根去掉余数部分
     * 算法：二分查找 但是有别于一般的经典的二分查找算法，我们需要对原始的二分查找进行一定的改进
     * 我们的目的是求解下述问题：
     *      max k*k <= x
     *       k
     * @param x
     * @return
     */
    public static int IntSqrt(int x) {
        int i = 0; int j = x / 2 + 1;
        int ans = -1;
        while (i <= j) {
            int mid = i + (j - i) / 2;
            if ((long) mid*mid <= x) {
                ans = mid;
                i = mid + 1;
            } else {
                j = mid - 1;
            }
        }
        return ans;
    }

    /**
     * 求出较为精确的平方根
     * 最后保留4位小数
     *
     * 牛顿切线法
     * 迭代公式： x[n+1] = x[n] - f(x[n]) / f'(x[n])
     * 此时的 f = x ^ 2 - a   f' = 2 * x
     * 所以上述迭代为 x[n+1] = x[n] - (x[n]*x[n] - a) / (2 * x[n])
     * @param x
     * @param epsion：精度
     * @return
     */
    public static double FloatSqrt(int a,double epsion) {
        double x = a; // 初始值
        while(Math.abs(- (x*x - a)/(2 * x)) >= epsion) {
            x = x - (x*x - a) / (2 * x);
        }
        return x;
    }
}
